COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂20-Oct-86  1455	RPG  	Remarks on Generic Functions 
C00025 ENDMK
C⊗;
∂20-Oct-86  1455	RPG  	Remarks on Generic Functions 
To:   common-lisp-object-system@SAIL.STANFORD.EDU    

This long note contains some remarks addressed to the comments made
regarding generic functions. I think that people on this list do not share
the same ultimate view of what generic functions are and how they can be
used.

To me there are 3 things that the concept of generic functions buys us:

	1. The ability to spread the definition of a generic function
	   among the places where the partial definitions make the most
	   sense.  This is accomplished by placing DEFMETHODs in the
	   places where the relevant classes are defined, for example.

	2. The ability to abstract the definition of a generic function
	   into parts (methods) that are conceptually independent.  This
	   is accomplished by splitting the definition of a generic
	   function into independent parts where each part is the partial
	   function definition for a particular set of classes - each part
	   is a method.  This leads to a new modularization technique.

	3. The separation of the inheritance of behavior from placement of
	   code. Generic functions select methods based on the structure
	   of the class lattice, but the generic functions are not
	   constrained to be stored within that lattice.

Up until now I've seen a deep appreciation of only the first point by
members of this working group. I think this is natural because the only
experience that members of this working group have had is with
DEFMETHOD-like generic function definition.

Here is a summary of what I take to be our understanding of the nature of
generic functions.

There is a new type of first-class object, called a `generic function.'
It can be FUNCALLed and APPLYed exactly as Common Lisp functions can be.
When the function cell of a symbol contains a generic function, we say
that the symbol, call it S, `names' the generic function and that the
generic function is associated with the name, S. [This is exactly as
things are in Common Lisp with respect to functions.] Using MAKE-GENERIC
it is possible to create a generic function not associated with any
symbol.

Generic functions have internal structure. This internal structure
includes the argument list, the argument precedence order, method
combination information, and `methods.'  Not required in that internal
structure is a `name' for the generic function.  A generic function, in
some implementations, might have a name as part of itself but only as an
informational device for use by programming environment tools. The correct
functioning of generic function cannot depend on that name.  When a
generic function is invoked, it invokes and combines some subset of the
methods. Which methods are invoked and how their results are combined
depends on the classes of the arguments supplied to the generic function
and on the method combination type of the generic function.

Methods are objects with, possibly, some internal structure - this has not
yet, I believe, been decided.  Methods include a function, called the
`method function,' and possibly some other user-visible information.  One
such possible part of the internal structure might be a pointer back to
the generic function of which the method is part.  The term `method' is
commonly used to refer to method objects.

Methods are associated with generic functions, but are not associated
directly with any names except in an informational sense - the correct
functioning of a method cannot depend on its name.  If a method is part of
a generic function which is associated with a symbol, S, we say that the
method is `defined for S.'  ADD-METHOD and GET-METHOD add methods to and
retrieve method objects from, respectively, generic functions. DEFMETHOD
adds a method to the generic function associated with the symbol that is
the first argument of DEFMETHOD.

Methods are possibly applicable objects - I don't believe this has been
decided yet.

(typep <generic-function> 'function) 

returns T, and possibly 

(typep <method-object> 'function)

does too. It is certainly possible to write the following code:

(labels ((f (x) ...g...)  ;calls g
	 (g (x) ...h...)  ;calls h
	 (h (x) ...f...)) ;calls f
 (add-method <gf> '((x c1)) #'f)
 (add-method <gg> '((x c2)) #'g)
 (add-method <gh> '((x c3)) #'h))

where <gf>, <gg>, and <gh> are generic functions. This defines
a set of methods whose method functions are mutually referential.
This does not imply that methods are directly invocable.

Generic functions are self-contained objects.  The parts of generic
functions are not spread out in the heap, in tables, or in the class
lattice: The parts are contained in the generic function. Pointers to
generic functions might appear in various places for the proper function
of tools.  One place is the class lattice, which defines the inheritance
structure on which the operation of generic functions depends. [Note:
an implementation is free to spread the definition wherever it likes
as long as it maintains the illusion of generic functions as first-class
objects.]

For example, environmental tools for associating methods with classes are
desirable.  These tools will enable us to browse through a class lattice
and display all methods that operate on instances of the classes being
browsed.  To do this, the tool must be able to determine for each class
the generic functions that operate on that class.  In the case where a
generic function is associated with a symbol, it is nice to display that
symbol as the name of the generic function (that is, as the operator).

FMAKUNBOUND can disrupt the correct functioning of this tool.
FMAKUNBOUND, when applied to a symbol with which a generic function is
associated, removes the generic function definition from the function cell
of the symbol.  FMAKUNBOUND cannot cause generic functions to behave
inconsistently with respect to their invocation semantics. 
[(SETF (SYMBOL-FUNCTION ...) ...) also cannot disrupt invocation semantics.]

Let's look at an example. Suppose the user writes

(DEFMETHOD FOO ((X C)) ...)

The tool that displays generic functions for the class C will undoubtedly
display FOO by name. What does the class C store? It can store only the
symbol, FOO, or it can store not only the symbol, FOO, but also the
generic function stored in FOO's function cell.  If the user does
(FMAKUNBOUND 'FOO) and the symbol alone is stored with the class, the tool
might display the wrong thing; if the user then does a second DEFMETHOD on
FOO, then the tool will very likely display the wrong thing. If the class
stores the symbol and the generic function, the tool can, after the
FMAKUNBOUND, display the anonymous generic function without the associated
name, FOO - assuming mutability of generic functions.

Possibly implementations that support tools like the one above will need a
function whose name could be REMOVE-GENERIC-FUNCTION-FROM-CLASS-LATTICE,
which removes from the class lattice all references to this generic
function. The primary client of this function will be the environment
tools.

Here is an example of some behavior I'd expect to see:

(DEFMETHOD FOO ((X C)) (FORMAT T "FOO, version 1, called on ~S~%" X))

<request to show the methods on C displays #<GENERIC-FUNCTION FOO>
and #<METHOD-OBJECT FOO> or something like that>
 
(FOO X) ;X an instance of C

causes

FOO, version 1, called on <X>

to be printed.

(SETQ BAZ #'FOO)

(FMAKUNBOUND 'FOO)

<request to show the methods on C displays #<GENERIC-FUNCTION 7128161>
and #<METHOD-OBJECT 86018603> or something like that>
 
(FOO X) ;X an instance of C

signals an error.

(DEFMETHOD FOO ((X C)) (FORMAT T "FOO, version 2, called on ~S~%" X))

<request to show the methods on C displays #<GENERIC-FUNCTION 7128161>
and #<METHOD-OBJECT 86018603> or something like that, and
#<GENERIC-FUNCTION FOO> and #<METHOD-OBJECT FOO> or something like that>

(FOO X) ;X an instance of C

causes 

FOO, version 2, called on <X>

and nothing else, to be printed.

(FUNCALL BAZ X) ;same X

causes

FOO, version 1, called on <X>

(SETQ BAZ NIL)

results in a situation in which the tool displays things that might
confuse the user. At this point the user might like to clean up the
environment

Now let's turn our attention to naming. Suppose someone writes:

;;; Define a recursive generic function
(DEFMETHOD FOO ((X C)) 
 ;; Do something useful
 (MUNCH X)
 ;; Do something related on a related class.
 (FOO (SOME-OTHER-CLASS X)))

(SETF (SYMBOL-FUNCTION 'BAZ) #'FOO)

(DEFMETHOD FOO ((X C1)) ...)

Oh dear, (BAZ <c, an instance of C>) might lose because the recursive call
in FOO refers to some other generic function than the one supposedly
intended when the code for the first DEFMETHOD on FOO was written.  Well,
we face the same problem with normal functions, and LABELS is used to
solve that:

(DEFUN FACT (N)
 (LABELS ((FACT (N) (IF (ZEROP N) 1 (* N (FACT (1- N))))))
  (FACT N)))

(FACT 47)
258623241511168180642964355153611979969197632389120000000000 

(SETF (SYMBOL-FUNCTION 'BAZ) #'FACT)

(DEFUN FACT (X)
 (FORMAT T "Adding ~S as a fact to the database!~% X)
 (ADD-FACT X)
 T)

(BAZ 47)
258623241511168180642964355153611979969197632389120000000000 

We should be able to define generic functions and methods that have this
degree of insulation from the accidents of naming.  Unless we define
something like GENERIC-FUNCTION-LABELS, the definition of such
self-contained generic functions will be ugly, containing FUNCALLs.

Some people have questioned whether it is a reasonable style to
write methods locally when it is clear that the intended purpose
of the standard is to let people write DEFMETHODs all over the place.

At the start of this message I mentioned several important things that
generic functions buy us. I will now paraphrase and expand on point number
2 above:


	   The concept of generic functions gives us the ability to
	   formulate the definition of a generic function as the
	   accumulation of methods, each modularly defined and each
	   specifically applicable to a set of classes. This enables the
	   programmer to formulate his code in natural pieces and to have
	   them assembled by the generic-function-calling mechanism.

The point behind my `lexically defined generic function' proposal is to
recognize and promulgate this programming methodology.  If it is a good
methodology to define generic functions that are associated with symbols
using this modular approach, then it should be a good methodology to
define anonymous generic functions the same way.  Using MAKE-GENERIC and
ADD-METHOD it is possible to do this, but at the expense of unreadable
code.

There is a second sort of `local' definition of methods that could make
sense - it is the one to which Gregor alluded in his message about my
anonymous generic function proposal. Suppose that a set of methods on the
symbol, FOO, has been defined. In a dynamic context the user might want
to temporarily extend FOO. I will use the name DFLET-METHOD; the user can
write:

(DFLET-METHOD ((FOO ((X C)) ...)) <form>)

and temporarily extend the generic function FOO to have this new method
associated with it during the execution of <form>. This, also, is a
reasonable programming methodology. I was curious about why Gregor thought
I meant something like DFLET-METHOD in my lexical generic function
proposal, even though I think my proposal was relatively clear on my
intention. I believe it is because Gregor thinks in terms of methods and
not in terms of generic functions.  In this long message I have used the
term `generic function' relentlessly, and I have made the distinction
between generic functions and methods clear.

Moon raised the objection that because no one has experience with lexical
generic functions they should not be considered for inclusion as part
of the standard. People have had experience with DEFMETHOD, and people
have had experience with FLET/LABELS. Therefore the combination of them is
not a far-out concept. No one has had experience with meta-objects and
method combination in one system, so should we invoke Moon's design
principle to exclude from consideration a system that has both?

In writing a standard, one tries to take well-known programming language
constructs and methodology and from them make reasonable improvements and
meldings.  Certainly when Common Lisp was being defined some risks were
taken in terms of adopting constructs that few people had experience with.
FLET/LABELS was familiar mostly to Steele and myself; the style of
multiple values adopted was sufficiently unlike others to be considered a
radical departure. The sequence functions were relatively unknown.

Let me relate the tale of TEX. Don Knuth designed TEX in 1977, and TEX78
contained one or two very powerful ideas for typesetting. The power of
these ideas captured the attention of people who care about typesetting
and beautiful manuscripts, to the extent that these people made a major
effort to convert their old documents to TEX.

Over a period of 4 years TEX was in heavy use, and people found that some
of the things they wanted to do were nearly impossible; people also found
that there were various TEX parameters that they wanted to control in
their macros. As with most non-Lisp-like languages, the macro facilities
were horrible.

Because Knuth adopted the design principle of retaining the existing
structure of TEX78 while taking strong consideration of the comments of
his loyal users, he decided to simply re-write TEX *adding* every facility
that was requested. There were approximately 200 of these facilities
added.  Rather than sitting back and thinking about what these critiques
meant - all suggestions for improvements are really critiques - and
re-designing TEX, he just added them to TEX with minimal structural
changes. In fact, the structural changes were mostly those needed to
accomodate the facilities the users requested.

When I hear people state that the overriding design consideration for the
object system is the needs that existing users express or that it is
important to retain a familiar structure while adding a few new facilities,
I am reminded of TEX84, the worst (but most powerful) typesetting language
in existence by far. Yes, we should keep the past firmly in mind, but
not blindly in mind.